package leetcode.string;

import java.util.Arrays;

/**
 * @author Cheng Jun
 * Description: s1 的排列之一是 s2 的 子串 。
 * 提示：
 * 1 <= s1.length, s2.length <= 10^4
 * s1 和 s2 仅包含小写字母
 * https://leetcode.cn/problems/permutation-in-string/
 * @version 1.0
 * @date 2022/8/4 9:43
 * 编程收获：一定要看题目给的提示或限制，从这题中的 s1和s2的长度限制来看，这题就适用回溯算法。因为这里回溯算法的时间复杂度为 O(n x n!)。
 * 所以一定要注意题目的提示或限制。
 * 提示中说 s1 和 s2 仅包含字母，其实就是在提示用数组去解题。
 */
public class checkInclusion {

    public static void main(String[] args) {
        String s1 = "adc";
        String s2 = "dcda";
        System.out.println(checkInclusion1(s1, s2));
    }

    private boolean res = false;

    /**
     * 回溯思想：尽快找到符合条件的子串。
     * 提交 LeetCode 超时
     *
     * @param s1
     * @param s2
     * @return boolean
     * @author Cheng Jun
     * @date 2022/8/4 9:45
     */
    @Deprecated
    public boolean checkInclusion(String s1, String s2) {
        if (s2.length() < s1.length()) return res;
        if (s2.contains(s1)) return true;
        char[] charArr = s1.toCharArray();
        Arrays.sort(charArr);
        backTrack(charArr, new boolean[charArr.length], 0, new StringBuilder(""), s2);
        return res;
    }

    private void backTrack(char[] charArr, boolean[] used, int deep, StringBuilder permute, String s2) {
        if (res == true) return;
        if (deep == charArr.length) {
            if (s2.contains(permute.toString())) res = true;
            return;
        }
        for (int i = 0; i < charArr.length; i++) {
            if (used[i] || (i != 0 && !used[i - 1] && charArr[i - 1] == charArr[i])) continue;
            used[i] = true;
            permute.append(charArr[i]);
            backTrack(charArr, used, deep + 1, permute, s2);
            permute.deleteCharAt(permute.length() - 1);
            used[i] = false;
        }
    }

    // 思路：这个题目其实是说，在s2的某一段长度为s1.length中 能完全匹配s1所出现的字符，个数也要一致
    // 在s2中确定一个长度为s1.length()的窗口，不断右移。
    static boolean checkInclusion1(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int[] s1CharArr = new int[26];
        int[] s2CharArr = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            int index = s1.charAt(i) - 97;
            s1CharArr[index] += 1;
        }
        for (int i = 0; i <= s2.length() - s1.length(); i++) {
            inner:
            for (int j = i; j < i + s1.length(); j++) {
                int index = s2.charAt(j) - 97;
                s2CharArr[index] += 1;
                if (s2CharArr[index] > s1CharArr[index]) {
                    Arrays.fill(s2CharArr, 0);
                    break inner;
                }
                if (j == (i + s1.length() - 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    // https://leetcode.cn/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/
    static boolean checkInclusion2(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = n; i < m; ++i) {
            ++cnt2[s2.charAt(i) - 'a'];
            --cnt2[s2.charAt(i - n) - 'a'];
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }

    // 最优解：滑动窗口+双指针
    static boolean checkInclusion3(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            // 在数组的对应位置，挖坑等着s2来填坑
            --cnt[s1.charAt(i) - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; right++) {
            int x = s2.charAt(right) - 'a';
            // s2填坑
            ++cnt[x];
            // 填多了，就要从把left往右移，直到这个位置填的刚刚好
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            // 如果左右指针间的个数等于 n，表示已经找到了
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }

}
